
class BbZo:
    def __init__(self,N:int,W:int,v:list,w:list):
        self.__N = N
        self.__W = W
        self.__v = v
        self.__w = w

    def DpSolution(self):
        #状态表示  dp[N][W] = V  表示的是第N个物品且背包容积为W时的最大价值
        #dp的初始状态

        dp = [[ self.__v[i] if j>=self.__w[i] and i==0  else 0 for j in range(self.__W+1)]   for i in range(self.__N)]
        for i in range(1,self.__N):
            for c in range(self.__W+1):
                dp[i][c] = dp[i-1][c]#不考虑当前的物品
                if c>=self.__w[i]:#考虑当前的物品时，必须满足条件
                    dp[i][c] = max(dp[i][c],self.__v[i]+dp[i-1][c-self.__w[i]])
        return dp[self.__N-1][self.__W]
    def MemoRecur(self):
        pass

if __name__ == '__main__':
    w = [2,2,3,3]#m每个物品的重量
    v = [2,4,4,5]#每个背包的价值
    s = BbZo(4,5,v,w)#第一个参数是背包的数量，第二个参数是背包的价值
    print(s.DpSolution())



